/**
 * 402. 移掉K位数字
 * https://leetcode-cn.com/problems/remove-k-digits/
 */
public class Solutions_402 {
    public static void main(String[] args) {
        String num = "1432219";
        int k = 3;  // output: "1219"

//        String num = "10200";
//        int k = 1;  // output: "200"

//        String num = "10";
//        int k = 2;  // output: "0"

//        String num = "10";
//        int k = 1;  // output: "0"

//        String num = "112";
//        int k = 1;  // output: "11"

        String result = removeKdigits(num, k);
        System.out.println(result);
    }

    /**
     * 单调（递增）栈实现
     */
    public static String removeKdigits(String num, int k) {
        int len = num.length();
        if (len == 0 || k == num.length()) {
            return "0";
        }
        char[] stack = new char[len];
        int idx = 0;

        char[] arr = num.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            char c = arr[i];
            while (k > 0 && idx > 0 && stack[idx - 1] > c) {
                // 当前字符小于前一字符时，前一字符可以“删除”
                idx --;
                k --;
            }
            if (c == '0' && idx == 0 && i != arr.length - 1) {
                // 字符 '0' 是否添加，取决于三个条件：
                // 1. 当前字符是 '0'
                // 2. idx 大于 0，即不会被添加到首位
                // 3. idx 是最后一位时，也要将 0 添加到 stack 中，num = "10"，k = 1 的情况
                //      否则结果为空串，正确结果应该是 "0"
                continue;
            }
            stack[idx++] = c;
        }
        if (k > 0) {
            // 此时的 stack 数组中，字符元素一定是升序排列的，即后面字符一定大于前面字符
            // 删除后面字符即可
            // num = "112"，k = 1 的情况
            idx -= k;
        }
        // 取 stack 中从 0 开始的 idx 位字符
        return new String(stack, 0, idx);
    }
}
